package com.xk._02算法篇._05backTracking;

import com.xk.tools.Times;

/**
 * @description: N皇后问题 -- 优化2
 * @author: xu
 * @date: 2022/10/16 20:06
 */
public class NQueens2 {
    public static void main(String[] args) {
        Times.test("testNQueen1", () -> new NQueens2().plate8Queens());
        //
        /*int n = 125;
        System.out.println(n);

        System.out.println(n >> 2);

        System.out.println(n);*/
    }

    private static final int EIGHT = 8;
    /**
     * 数组索引是行号，数组列数是列号
     */
    int[] queens;
    /**
     * 标记着某一位是否有皇后了
     */
    byte cols;
    /**
     * 标记着某一对角线是否有皇后了（左上角 --> 右下角  left top --> right bottom）
     */
    short leftTop;
    /**
     * 标记着某一对角线是否有皇后了（右上角 --> 左下角  right top --> left bottom）
     */
    short rightTop;
    /**
     * 一共有多少种合理的摆法
     */
    int ways;

    void plate8Queens() {
        queens = new int[EIGHT];
        place(0);
        System.out.println("8皇后一共有" + ways + "种摆法");
    }

    /**
     * 从第 row 行开始摆放皇后
     * @param row
     */
    void place(int row){
        if (row == EIGHT) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < EIGHT; col++) {
            // 剪枝处理
            // 条件也可以写成: cols & (1 << col) != 0
            if (((cols >> col) & 1) == 1) continue;
            int ltIndex = row - col + EIGHT - 1;
            int rtIndex = row + col;
            if (((leftTop >> ltIndex) & 1) == 1 || ((rightTop >> rtIndex) & 1) == 1) continue;

            // 在第row行，第col列摆放皇后 对应的位必为0
            cols |= (1 << col);
            leftTop |= (1 << ltIndex);
            rightTop |= (1 << rtIndex);
            queens[row] = col;
            place(row + 1);

            // 状态重置：对应的位必为1
            cols ^= (1 << col);
            leftTop ^= (1 << ltIndex);
            rightTop ^= (1 << rtIndex);
        }
    }

    void show(){
        for (int row = 0; row < EIGHT; row++) {
            for (int col = 0; col < EIGHT; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("=====================");
    }
}
